package study.translation.grammar;

import org.apache.log4j.Logger;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class BNFParser
{
    private static final Logger log = Logger.getLogger( BNFParser.class );

    private static Pattern rulePattern = Pattern.compile( "^\\s*<([a-z ]+?)>\\s*::=\\s*(.*)\\s*$", Pattern.CASE_INSENSITIVE );

    private enum State
    {
        INITIAL( 0 ),
        PARSING_NONTERMINAL( 1 ),
        PARSING_TERMINAL( 2 ),
        PARSING_SYMBOL( 3 ),
        ERROR( -1 );

        int index;

        State( int index )
        {
            this.index = index;
        }

        static State valueOf( int index )
        {
            for( State s : State.values() )
            {
                if( s.index == index )
                {
                    return s;
                }
            }
            return null;
        }
    }

    private enum SymbolClass
    {
        NONTERM_START( 0 ),
        NONTERM_END( 1 ),
        SYMBOL_BOUNDS( 2 ),
        SPACE( 3 ),
        OTHER( 4 );

        int index;

        private SymbolClass( int index )
        {
            this.index = index;
        }
    }

    /**
     * Finite automate matrix (-1 means error).
     */
    private static int[][] matrix = {
            // 0 - '<', 1 - '>', 2 - '\'', 3 - space, 4 - other character
            { 1, -1, 3, 0, 2 }, // 0 - Initial state
            { -1, 0, -1, 1, 1 }, // 1 - Parsing nonterminal symbol
            { 1, -1, 3, 0, 2 }, // 2 - Parsing terminal symbol
            { -1, -1, 0, 3, 3 } // 3 - Parsing terminal character enclosed between ''
    };

    public Grammar parse( InputStream stream ) throws IOException, ParseException
    {
        Grammar descriptor = new Grammar();
        BufferedReader reader = new BufferedReader( new InputStreamReader( stream ) );
        String line, ruleName = null, rightPart = null;
        while( null != ( line = reader.readLine() ) )
        {
            Matcher m = rulePattern.matcher( line );
            if( m.matches() )
            {
                // New rule matched, save previous one
                if( ( null != ruleName ) && ( null != rightPart ) )
                {
                    parseRule( descriptor, ruleName, rightPart );
                }
                ruleName = m.group( 1 );
                rightPart = m.group( 2 );
            }
            else if( null != rightPart )
            {
                // Continue from next line
                rightPart += line.trim();
            }
        }
        if( ( null != ruleName ) && ( null != rightPart ) )
        {
            parseRule( descriptor, ruleName, rightPart );
        }
        log.debug( descriptor.toBNF( true ) );
        return descriptor;
    }

    private void parseRule( Grammar descriptor, String ruleName, String rightPart ) throws ParseException
    {
        Nonterminal n = descriptor.createNonterminal( ruleName );
        StringTokenizer tokenizer = new StringTokenizer( rightPart, "|" );
        while( tokenizer.hasMoreTokens() )
        {
            String part = tokenizer.nextToken().trim();
            if( part.isEmpty() )
            {
                // Add e-rule
                descriptor.addRule( new Rule( n, new ArrayList<Symbol>() ) );
            }
            else
            {
                List<Symbol> symbols = parseSymbols( descriptor, part );
                descriptor.addRule( new Rule( n, symbols ) );
            }
        }
        if( rightPart.endsWith( "|" ) )
        {
            // Add e-rule
            descriptor.addRule( new Rule( n, new ArrayList<Symbol>() ) );
        }
    }

    private List<Symbol> parseSymbols( Grammar descriptor, String input ) throws ParseException
    {
        int substr = 0;
        List<Symbol> symbols = new LinkedList<Symbol>();
        State state = State.INITIAL;
        char[] chars = input.toCharArray();
        for( int i = 0; i < chars.length; i++ )
        {
            int j = getSymbolClass( chars[ i ] ).index;
            State newState = State.valueOf( matrix[ state.index ][ j ] );
            if( newState.equals( State.ERROR ) )
            {
                throw new ParseException( "Error parsing grammar near \"" + input.substring( substr ) + "\"" );
            }
            else if( !state.equals( newState ) )
            {
                switch( state )
                {
                    case PARSING_NONTERMINAL:
                        symbols.add( descriptor.createNonterminal( input.substring( substr + 1, i ) ) );
                        break;

                    case PARSING_TERMINAL:
                        symbols.add( new Terminal( input.substring( substr, i ).trim() ) );
                        break;

                    case PARSING_SYMBOL:
                        symbols.add( new Terminal( input.substring( substr + 1, i ) ) );
                        break;
                }
                substr = i;
            }
            state = newState;
        }
        switch( state )
        {
            case PARSING_TERMINAL:
                symbols.add( new Terminal( input.substring( substr ) ) );
                break;

            case PARSING_NONTERMINAL:
            case PARSING_SYMBOL:
                System.out.println( "Error parsing gramar near " + input.substring( substr ) );
                System.exit( -1 );
                break;
        }
        return symbols;
    }

    private SymbolClass getSymbolClass( char c )
    {
        switch( c )
        {
            case '<':
                return SymbolClass.NONTERM_START;
            case '>':
                return SymbolClass.NONTERM_END;
            case '\'':
                return SymbolClass.SYMBOL_BOUNDS;
            case ' ':
            case '\t':
            case '\n':
                return SymbolClass.SPACE;
            default:
                return SymbolClass.OTHER;
        }
    }
}
